package com.desheng.bigdata.ds.tree;

/**
 * @Description 红黑树，其实是对2-3查找树的简单实现
 *      所谓2-3查找树，就是一颗树中，既可以有2节点，也可以有3节点。
 *      这里所谓的2节点，就是一个节点，最多可以有2个子节点，并且该节点只能有一组k-v。
 *      这里所谓的3节点，就是一个节点，最多可以有3个子节点，并且该节点有两组k-v。
 *      这些节点和子节点的关系是如果为2节点，左子节点的key小于该节点，右子节点的key大于该节点。
 *      3节点的左子节点的key小于该节点第一组的k，中间节点的key，大于第一组k，小于第二组k，右子节点的key大于该节点的第二组key。
 *   红黑树是含有红黑链接并满足下列条件的二叉查找树：
 *    1. 红链接均为左链接；
 *    2. 没有任何一个结点同时和两条红链接相连；
 *    3. 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同；
 *
 * 平衡化：
 *  在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。
 * 解决平衡化的方式，
 *  左旋
 *      当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。
 *  右旋
 *      当某个节点的左子节点为红色，并且左子节点的左子节点也为红色，此时需要右旋。
 *  颜色反转
 *       当某个节点的左右子节点都为红色，此时需要颜色反转
 *  结论：红黑树的根节点的颜色总是黑色的
 * @Author deshenglijun
 * @Date 2020/6/1 21:32
 * @Version 1.0
 */
public class RedBlackTree<K extends Comparable<K>, V> {

    private Node<K, V> root;//记录根节点
    private int size;//记录树中元素的个数
    private static final boolean RED = true;//红色连接标识
    private static final boolean BLACK = false;//黑色连接标识

    class Node<K extends Comparable<K>, V> {
        public Node<K, V> left; //记录该节点的左子节点
        public Node<K, V> right; //记录该节点的右子节点
        public K key; // 存储该节点的key
        public V value; // 存储该节点的value
        public boolean color;//由该节点父节点指向自身的链接，如果是red，则为true

        public Node(K key, V value, Node<K, V> left, Node<K, V> right, boolean color) {
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
            this.color = color;
        }
    }

    /**
     * 判断当前结点的父指向链接是否为红色
     */
    private boolean isRed(Node<K, V> node) {
        if(node == null) {
            return false;
        }
        return node.color;
    }

    /**
     * 左旋调整
     *  当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。
     * @param node
     * @return
     */
    private Node<K, V> rotateLeft(Node<K, V> node) {
        Node<K, V> rightNode = node.right;

        node.right = rightNode.left;

        rightNode.left = node;

        rightNode.color = node.color;

        node.color = true;
        return rightNode;
    }

    /**
     * 右旋调整
     *  当某个节点的左子节点为红色，并且左子节点的左子节点也为红色，此时需要右旋。
     * @param node
     * @return
     */
    private Node<K, V> rotateRight(Node<K, V> node) {
        Node<K, V> leftNode = node.left;
        node.left = leftNode.right;
        leftNode.right = node;
        leftNode.color = node.color;
        node.color = true;
        return leftNode;
    }

    /**
     * 颜色反转，相当于完成拆分4-结点
     * @param node
     */
    private void flipColor(Node<K, V> node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    /**
     * 向红黑树中插入一个节点
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        root = put(root, key, value);
        root.color = BLACK;
    }
    /*
        插入方法的重载方法，在指定的节点处拆入一个节点。
     */
    private Node<K, V> put(Node<K, V> node, K key, V value) {
        if(node == null) {//构建只有一个节点的树，节点颜色为红色
            size++;
            return new Node<>(key, value, null, null, RED);
        }
        //进行比较插入元素
        int compared = key.compareTo(node.key);
        if(compared < 0) {
            node.left = put(node.left, key, value);
        } else if(compared > 0) {
            node.right = put(node.right, key, value);
        } else {
            node.value = value;
        }
        //左旋
        if(isRed(node.right) && !isRed(node.left)) {
            node = rotateLeft(node);
        }
        //右旋
        if(isRed(node.left) && isRed(node.left.left)) {
            node = rotateRight(node);
        }
        //颜色反转
        if(isRed(node.left) && isRed(node.right)) {
            flipColor(node);
        }
        return node;
    }
    /*
        获取指定树中key对应的value
     */
    public V get(K key) {
        return get(root, key);
    }
    /*
        获取指定树node中得key对应的value
     */
    private V get(Node<K, V> node, K key) {
        if(node == null) {
            return null;
        }
        int compared = key.compareTo(node.key);
        if(compared < 0) {
            return get(node.left, key);
        } else if(compared > 0) {
            return get(node.right, key);
        } else {
            return node.value;
        }
    }

    public int size() {
        return this.size;
    }
}
